#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../include/insertsort.h"

using namespace std;

const int SPACE_SIZE = 100;

// 快速排序
// 1.从数列中挑出一个元素，称为 “基准”（pivot）。
// 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
// 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。


// 快速排序
// 1.选取基准值时，使用三数取中，避免最坏情况发生。
// 2.当快排到一定区间时，使用插入排序

// 时间和空间复杂度
// 情况	时间复杂度	发生条件
// 最优情况	O(n log n)	每次分区都能将数组均匀分成两半
// 平均情况	O(n log n)	随机数据分布
// 最坏情况	O(n²)	每次分区极度不平衡（如已排序数组+简单基准选择）

// 空间复杂度分析
// 情况	空间复杂度	说明
// 最优情况	O(log n)	平衡分区时的递归栈深度
// 最坏情况	O(n)	完全不平衡时的递归栈深度

// 不稳定排序

// 三值取中法选择基准值
int medianOfThree(int arr[], int left, int right) {
    int mid = left + (right - left) / 2;
    
    // 对左、中、右三个元素进行排序
    if (arr[right] < arr[left])
        swap(arr[left], arr[right]);
    if (arr[mid] < arr[left])
        swap(arr[mid], arr[left]);
    if (arr[right] < arr[mid])
        swap(arr[right], arr[mid]);
    
    // 返回中间值的索引
    return mid;
}

int partition(int arr[], int left, int right) {
    // 选择基准值
    // 不选择第一个值，避免劣化排序
    // 三值取中法
    int mid = medianOfThree(arr, left, right);
    int pivot = arr[mid];
    int i = left - 1;
    int j = right + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        
        if (i >= j) {return j;}
        
        swap(arr[i], arr[j]);
    }
}

void QuickSort(int arr[], int left, int right) {
    // 递归结束条件
    if (arr == nullptr || left >= right)
        return;

    // 当区间小于 SPACE_SIZE 时，使用插入排序
    // 因为快排最后接近有序，使用插入排序效率更高
    if (right - left + 1 < SPACE_SIZE)
    {
        InsertSort(arr + left, right - left + 1);
        return ;
    }
    

    // 选择基准值
    // 1. Hoare分区方案（当前实现）
    // 特点：
    
    // 使用两个指针（i从左侧开始，j从右侧开始）向中间扫描
    // 不需要将基准值放到最终位置
    // 分区后仅保证左分区 ≤ 右分区
    // 递归边界为[left, pos]和[pos+1, right]

    // 2. Lomuto分区方案（替代方案）
    // 特点：
    
    // 单指针（i）从左到右扫描，维护一个“小于基准值”的区间
    // 基准值最终会被放到正确位置
    // 递归边界为[left, p-1]和[p+1, right]
    // 实现更简单，但交换次数较多

    // 两种方案的对比
    // 特性	Hoare方案	Lomuto方案
    // 分区效率	更高（交换次数少）	较低（交换次数多）
    // 基准值位置	不保证在最终位置	保证在最终位置
    // 递归边界	[left, pos]和[pos+1, right]	[left, p-1]和[p+1, right]
    // 实现复杂度	稍复杂	更简单
    // 对重复元素的处理	更均衡	可能导致不平衡分区
    // 适用场景	通用场景	教学或简单实现
    int pos = partition(arr, left, right);

    // 递归
    QuickSort(arr, left, pos);
    QuickSort(arr, pos + 1, right);
}

void QuickSort(int arr[], int size) {
    if (size <= 1)
        return;

    QuickSort(arr, 0, size - 1);
}


// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     QuickSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }


